class dcu
{
public:
	void init(int);
	int root(int);
	void join(int, int);
private:
	vector <int> anc;
};

void dcu::init(int n)
{
	srand(n | 1 << n);
	anc.resize(n);
	forx(i, n)
		anc[i] = i;
}

int dcu::root(int v)
{
	return
		(v == anc[v])
			? v
			: anc[v] = root(anc[v]);
}

void dcu::join(int a, int b)
{
	a = root(a);
	b = root(b);
	if (rand() & 1)
		swap(a, b);
	if (a != b)
		anc[a] = b;
}